package com.sosky;

import java.util.Arrays;

/**
 * 1027. 最长等差数列
 * <p>
 * 给定一个整数数组 A，返回 A 中最长等差子序列的长度。
 * <p>
 * 回想一下，A 的子序列是列表 A[i_1], A[i_2], ..., A[i_k] 其中 0 <= i_1 < i_2 < ... < i_k <= A.length - 1。
 * 并且如果 B[i+1] - B[i]( 0 <= i < B.length - 1) 的值都相同，那么序列 B 是等差的。
 * <p>
 * 示例 1：
 * <p>
 * 输入：[3,6,9,12]
 * 输出：4
 * 解释：
 * 整个数组是公差为 3 的等差数列。
 * 示例 2：
 * <p>
 * 输入：[9,4,7,2,10]
 * 输出：3
 * 解释：
 * 最长的等差子序列是 [4,7,10]。
 * 示例 3：
 * <p>
 * 输入：[20,1,15,3,10,5,8]
 * 输出：4
 * 解释：
 * 最长的等差子序列是 [20,15,10,5]。
 */
public class Solution1027 {
    public static void main(String[] args) {
        System.out.println(longestArithSeqLength(new int[]{3, 6, 9, 12}));
        System.out.println(longestArithSeqLength(new int[]{9, 4, 7, 2, 10}));
        System.out.println(longestArithSeqLength(new int[]{20, 1, 15, 3, 10, 5, 8}));
    }

    public static int longestArithSeqLength(int[] A) {
        Arrays.sort(A);
        if (A.length == 2) {
            return 2;
        }
        int length = 0;
        for (int i = 0; i < A.length - 1; i++) {
            int arith = A[i + 1] - A[i];
            int count = 2;
            for (int j = i + 1; j < A.length - 1; j++) {
                for (int k = j + 1; k < A.length - 1; k++) {
                    if (A[k] - A[j] == arith) {
                        count++;
                    } else {
                        break;
                    }
                }
            }
            if (count > length) {
                length = count;
            }
        }
        return length;
    }
}
